package com.currentbp.Interesting.likou.complete;

import org.junit.Test;

import java.util.*;

/**
 * @author baopan
 * @createTime 2024/3/19 21:53
 */
public class T1287getKth {
    /*
我们将整数 x 的 权重 定义为按照下述规则将 x 变成 1 所需要的步数：
如果 x 是偶数，那么 x = x / 2
如果 x 是奇数，那么 x = 3 * x + 1
比方说，x=3 的权重为 7 。因为 3 需要 7 步变成 1 （3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）。
给你三个整数 lo， hi 和 k 。你的任务是将区间 [lo, hi] 之间的整数按照它们的权重 升序排序 ，如果大于等于 2 个整数有 相同 的权重，那么按照数字自身的数值 升序排序 。
请你返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。
注意，题目保证对于任意整数 x （lo <= x <= hi） ，它变成 1 所需要的步数是一个 32 位有符号整数。
示例 1：
输入：lo = 12, hi = 15, k = 2
输出：13
解释：12 的权重为 9（12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）
13 的权重为 9
14 的权重为 17
15 的权重为 17
区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ，答案是第二个整数也就是 13 。
注意，12 和 13 有相同的权重，所以我们按照它们本身升序排序。14 和 15 同理。
示例 2：
输入：lo = 7, hi = 11, k = 4
输出：7
解释：区间内整数 [7, 8, 9, 10, 11] 对应的权重为 [16, 3, 19, 6, 14] 。
按权重排序后得到的结果为 [8, 10, 11, 7, 9] 。
排序后数组中第 4 个数字为 7 。
     */
    /*
    解题思路：
    1、计算出所有数的权重，
    1.1、获取一个数的权重时，可以将一个数的每步记录下来
    2、写一个对fair的排序
    3、获取第k个数
     */
    @Test
    public void t1() {
        System.out.println(getKth(12, 15, 2));
        System.out.println(getKth(7, 11, 4));
    }

    public int getKth(int lo, int hi, int k) {
        //pair: weight->num
        List<MyPair> weights = getWeight(lo, hi);
        List<MyPair> sorts = getSort(weights);

        return sorts.get(k - 1).getRight();
    }

    //https://blog.csdn.net/susu1083018911/article/details/126362140     排序讲解
    private List<MyPair> getSort(List<MyPair> weights) {
        weights.sort(Comparator.comparing(MyPair::getLeft).thenComparing(MyPair::getRight));
        return weights;
    }

    private List<MyPair> getWeight(int lo, int hi) {
        List<MyPair> result = new ArrayList<>();
        for (int i = lo; i <= hi; i++) {
            int eachWeight = getEachWeight(i);
            result.add(new MyPair(eachWeight, i));
        }
        return result;
    }

    Map<Integer, Integer> eachWeightMap = new HashMap<>();

    {
        eachWeightMap.put(1, 0);
        eachWeightMap.put(2, 1);
    }

    class MyPair {
        Integer left;
        Integer right;

        public MyPair(int left, int right) {
            this.left = left;
            this.right = right;
        }

        public Integer getLeft() {
            return left;
        }

        public Integer getRight() {
            return right;
        }
    }

    private int getEachWeight(int x) {
        if (eachWeightMap.get(x) != null) {
            return eachWeightMap.get(x);
        }
        int eachWeight = 0;
        if (x % 2 == 0) {
            eachWeight = getEachWeight(x / 2) + 1;

        } else {
            eachWeight = getEachWeight(x * 3 + 1) + 1;
        }
        eachWeightMap.put(x, eachWeight);
        return eachWeight;
    }
}
